#include<iostream>
#include<cstdlib>
#include<cstdio>
#define inf 100000000
#define N 200001
#define M 3000001
using namespace std;
int n,m,sz,tmp,a[N];
int ls[M],rs[M],rnd[M],v[M],s[M],w[M];
int root[N];
void update(int k)
{s[k]=s[ls[k]]+s[rs[k]]+w[k];}
void rturn(int &k)
{int t=ls[k];ls[k]=rs[t];rs[t]=k;s[t]=s[k];update(k);k=t;}
void lturn(int &k)
{int t=rs[k];rs[k]=ls[t];ls[t]=k;s[t]=s[k];update(k);k=t;}
void insert(int &k,int num)
{
	if(!k){k=++sz;s[k]=w[k]=1;v[k]=num;rnd[k]=rand();return;}
	s[k]++;
	if(num==v[k])w[k]++;
	else if(num<v[k]){insert(ls[k],num);if(rnd[ls[k]]<rnd[k])rturn(k);}
	else {insert(rs[k],num);if(rnd[rs[k]]<rnd[k])lturn(k);}
}
void del(int &k,int num)
{
	if(v[k]==num)
	{
		if(w[k]>1){w[k]--;s[k]--;return;}
		if(ls[k]*rs[k]==0)k=ls[k]+rs[k];
		else if(rnd[ls[k]]<rnd[rs[k]]){rturn(k);del(k,num);}
		else {lturn(k);del(k,num);}
	}
	else if(num<v[k])
	{del(ls[k],num);s[k]--;}
	else {del(rs[k],num);s[k]--;}
}
void build(int k,int l,int r,int x,int num)
{
	insert(root[k],num);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)build(k<<1,l,mid,x,num);
	else build(k<<1|1,mid+1,r,x,num);
}
void ask_rank(int k,int num)
{
	if(!k)return;
	if(num==v[k]){tmp+=s[ls[k]];return;}
	else if(num<v[k])ask_rank(ls[k],num);
	else {tmp+=s[ls[k]]+w[k];ask_rank(rs[k],num);}
}
void get_rank(int k,int l,int r,int x,int y,int num)
{
	if(l==x&&r==y){ask_rank(root[k],num);return;}
	int mid=(l+r)>>1;
	if(mid>=y)get_rank(k<<1,l,mid,x,y,num);
	else if(mid<x)get_rank(k<<1|1,mid+1,r,x,y,num);
	else
	{
		get_rank(k<<1,l,mid,x,mid,num);
		get_rank(k<<1|1,mid+1,r,mid+1,y,num);
	}
}
void get_index(int x,int y,int z)
{
	int l=0,r=inf,ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		tmp=1;get_rank(1,1,n,x,y,mid);
		if(tmp<=z){l=mid+1;ans=mid;}
		else r=mid-1;
	}
	printf("%d\n",ans);
}
void change(int k,int l,int r,int x,int num,int y)
{
	del(root[k],y);
	insert(root[k],num);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(x<=mid)change(k<<1,l,mid,x,num,y);
	else change(k<<1|1,mid+1,r,x,num,y);
}
void before(int k,int num)
{
	if(!k)return;
	if(v[k]<num){tmp=max(v[k],tmp);before(rs[k],num);}
	else before(ls[k],num);
}
void after(int k,int num)
{
	if(!k)return;
	if(v[k]>num){tmp=min(v[k],tmp);after(ls[k],num);}
	else after(rs[k],num);
}
void ask_after(int k,int l,int r,int x,int y,int num)
{
	if(l==x&&r==y){after(root[k],num);return;}
	int mid=(l+r)>>1;
	if(mid>=y)ask_after(k<<1,l,mid,x,y,num);
	else if(mid<x)ask_after(k<<1|1,mid+1,r,x,y,num);
	else
	{
		ask_after(k<<1,l,mid,x,mid,num);
		ask_after(k<<1|1,mid+1,r,mid+1,y,num);
	}
}
void ask_before(int k,int l,int r,int x,int y,int num)
{
	if(l==x&&r==y){before(root[k],num);return;}
	int mid=(l+r)>>1;
	if(mid>=y)ask_before(k<<1,l,mid,x,y,num);
	else if(mid<x)ask_before(k<<1|1,mid+1,r,x,y,num);
	else
	{
		ask_before(k<<1,l,mid,x,mid,num);
		ask_before(k<<1|1,mid+1,r,mid+1,y,num);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)build(1,1,n,i,a[i]);
	for(int i=1;i<=m;i++)
	{
		int f;scanf("%d",&f);
		int x,y,k;
		switch(f)
		{
			case 1:scanf("%d%d%d",&x,&y,&k);tmp=1;get_rank(1,1,n,x,y,k);printf("%d\n",tmp);break;
			case 2:scanf("%d%d%d",&x,&y,&k);get_index(x,y,k);break;
			case 3:scanf("%d%d",&x,&y);change(1,1,n,x,y,a[x]);a[x]=y;break;
			case 4:scanf("%d%d%d",&x,&y,&k);tmp=0;ask_before(1,1,n,x,y,k);printf("%d\n",tmp);break;
			case 5:scanf("%d%d%d",&x,&y,&k);tmp=inf;ask_after(1,1,n,x,y,k);printf("%d\n",tmp);break;
		} 
	}
	return 0;
}
